/* 698. 划分为k个相等的子集 */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
/* dfs + 剪枝 */
let nums, n, t, k
var canPartitionKSubsets = function (_nums, _k) {
	nums = _nums
	k = _k
	let tot = 0
	for (const x of nums) tot += x
	if (tot % K) return false
	nums.sort((a, b) => a - b)
	n = nums.length
	t = tot / k
	return dfs(n - 1, 0, 0, new Array(n).fill(false))
}
function dfs(idx, cur, cnt, vis) {
	if (cnt === k) return true
	if (cur === t) return dfs(n - 1, 0, cnt + 1, vis)
	for (let i = idx; i >= 0; i--) {
		if (vis[i] || cur + nums[i] > t) continue
		vis[i] = true
		if (dfs(idx - 1, cur + nums[i], cnt, vis)) return true
		vis[i] = false
		if (cur == 0) return false
	}
	return false
}
const result = canPartitionKSubsets([1, 1, 1, 1, 2, 2, 2, 2], 2)
console.log('canPartitionKSubsets :>>', result)
